package algorithm.floyd;

import java.util.Arrays;

public class FloydAlgorithm {

  public static void main(String[] args) {
    char[] vertex = {'A','B','C','D','E','F','G'};
    final int N = 65535;
    int[][]matrix = new int[][]{
            {0,5,7,N,N,N,2},
            {5,0,N,9,N,N,3},
            {7,N,0,N,8,N,N},
            {N,9,N,0,N,4,N},
            {N,N,8,N,0,5,4},
            {N,N,N,4,5,0,6},
            {2,3,N,N,4,6,0}
    };
    Graph graph = new Graph(vertex.length,matrix,vertex);
//    测试
    graph.floyd();
    graph.show();
  }

}
class Graph{
  private char[]vertex;//存放顶点
  private int[][]dis;//保存，从各个顶点出发到其它顶点的距离，最后的结果，也是保留在该数组
  private int[][]pre;//保存到达目标顶点的前驱顶点

  public Graph(int length,int[][]matrix,char[]vertex){
    this.dis = matrix;
    this.vertex = vertex;
    this.pre = new int[length][length];
    
//    初始化pre
    for (int i = 0; i < length; i++) {
      Arrays.fill(pre[i],i);
    }
  }
//  显示数组的方法
  public void show(){
    char[] vertex = {'A','B','C','D','E','F','G'};
    for (int i = 0; i < dis.length; i++) {
      for (int j = 0; j < dis.length; j++) {
        System.out.print(vertex[pre[i][j]] + " ");
      }
      System.out.println();
      for (int j = 0; j < dis.length; j++) {
        System.out.print("(" +vertex[i] + "到" + vertex[j] + "的距离为" + dis[i][j] + ") ");
      }
      System.out.println();
    }
  }
//  floyd算法
  public void floyd(){
    int len = 0;
//    中间节点
    for (int k = 0; k < dis.length; k++) {
//      起点
      for (int i = 0; i < dis.length; i++) {
//        终点
        for (int j = 0; j < dis.length; j++) {
          len = dis[i][k] + dis[k][j];//求出从i顶点出发,经过k中间顶点,到达j顶点距离
          if (len < dis[i][j]){//如果len小于此时的距离，更新
            dis[i][j] = len;
            pre[i][j] = pre[k][j];//更新前驱节点
          }
        }
      }
    }
  }
}
